package com.cqs.leetcode.ds.union.find;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * lixw
 * 2021/11/6
 **/
public class EqualityEquations990 {

    public boolean equationsPossible(String[] equations) {
        int[] groups = new int[26];

        for (int i = 0; i < groups.length; i++) {
            groups[i] = 'a' + i;
        }

        //第一遍处理==情况
        for (String s : equations) {
            char l = s.charAt(0);
            char r = s.charAt(3);
            if (s.charAt(1) == '=') {
                int min = Math.min(l, r);
                int gl = groups[l-'a']; //一定要保存不被修改
                int gr = groups[r-'a'];
                int min2 = Math.min(gl, gr);
                min = Math.min(min,min2);
                //更新所有的节点
                for (int i = 0; i < 26; i++) {
                    if (groups[i] == gl || groups[i] == gr ) {
                        groups[i] = min;
                    }
                }
                groups[l - 'a'] = min;
                groups[r - 'a'] = min;

            }
        }

        //第二遍处理不等于
        for (String s : equations) {
            char l = s.charAt(0);
            char r = s.charAt(3);
            if (s.charAt(1) == '!' && groups[l-'a'] == groups[r-'a']) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<String[]> list = new ArrayList<>();
        list.add(new String[]{"a==b","d==c","a!=d","b==c"});
        list.add(new String[]{"a==b","b!=a"});
        list.add(new String[]{"b==a","a==b"});
        list.add(new String[]{"a==b","b==c","a==c"});
        list.add(new String[]{"a==b","b!=c","c==a"});
        list.add(new String[]{"a==b","d==c","a==d","b==c"});
        list.add(new String[]{"a!=b","b!=c","a==c"});
        EqualityEquations990 e = new EqualityEquations990();
        for (String[] t : list) {
            boolean b = e.equationsPossible(t);
            System.out.println(Arrays.asList(t) + "\t ---> " + b);
        }

    }
}
